package alice.exercise.leetcode.middle;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Alice
 * @since 2023-02-06 星期一 9:23
 */
class Solution {

  // 2536. 子矩阵元素加 1
  public int[][] rangeAddQueries(int n, int[][] queries) {
    int[][] diff = new int[n + 1][n + 1];
    for (int[] query : queries) {
      int startRow = query[0];
      int startCol = query[1];
      int endRow = query[2];
      int endCol = query[3];
      diff[startRow][startCol]++;
      diff[startRow][endCol + 1]--;
      diff[endRow + 1][startCol]--;
      diff[endRow + 1][endCol + 1]++;
    }
    int[][] arr = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int left = j == 0 ? 0 : arr[i][j - 1];
        int top = i == 0 ? 0 : arr[i - 1][j];
        int leftTop = (i == 0 || j == 0) ? 0 : arr[i - 1][j - 1];
        // arr[i][j] = (left + diff[i][j]) + (top + diff[i][j]) - (leftTop + diff[i][j]);
        arr[i][j] = diff[i][j] + left + top - leftTop;
      }
    }
    return arr;
  }

  // 3228. 将1移动到末尾的最大操作次数
  public int maxOperations(String s) {
    int oneCount = 0;
    int totalCount = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '1') {
        oneCount++;
      } else if (i > 0 && s.charAt(i - 1) == '1') {
        totalCount += oneCount;
      }
    }
    return totalCount;
  }

  // 1041. 困于环中的机器人
  public boolean isRobotBounded(String instructions) {
    char[] chars = instructions.toCharArray();
    int[] location = new int[]{0, 0};
    int toward = 0;
    int[][] dict = new int[][]{
      // 上
      new int[]{1, 1},
      // 右
      new int[]{0, 1},
      // 下
      new int[]{1, -1},
      // 左
      new int[]{0, -1}
    };
    for (int k = 0; k < 4; k++) {
      for (char c : chars) {
        switch (c) {
          case 'G':
            location[dict[toward][0]] += dict[toward][1];
            break;
          case 'L':
            toward = (toward + 3) % 4;
            break;
          case 'R':
            toward = (toward + 1) % 4;
            break;
          default:
            break;
        }
      }
      if (location[0] == 0 && location[1] == 0) {
        return true;
      }
    }
    return false;
  }

  // 1637. 两点之间不包含任何点的最宽垂直区域
  public int maxWidthOfVerticalArea1(int[][] points) {
    Set<Integer> set = new TreeSet<>();
    for (int[] point : points) {
      set.add(point[0]);
    }
    int pre = -1, max = 0;
    for (Integer i : set) {
      if (pre != -1) {
        max = Math.max(max, i - pre);
      }
      pre = i;
    }
    return max;
  }

  public int maxWidthOfVerticalArea(int[][] points) {
    Arrays.sort(points, Comparator.comparingInt(p -> p[0]));
    int max = 0, pre = -1;
    for (int[] point : points) {
      if (pre != -1) {
        max = Math.max(max, point[0] - pre);
      }
      pre = point[0];
    }
    return max;
  }

  // 1641. 统计字典序元音字符串的数目
  public int countVowelStrings(int n) {
    long l = (long) n;
    long x1 = l + 1;
    long x2 = l + 2;
    long x3 = l + 3;
    long x4 = l + 4;
    return (int) (x1 * x2 * x3 * x4 / 24);
  }

  // TODO 1574. 删除最短的子数组使剩余数组有序
  public int findLengthOfShortestSubarray(int[] arr) {
    return 0;
  }

  // 1630. 等差子数组
  public List<Boolean> checkArithmeticSubarrays1(int[] nums, int[] l, int[] r) {
    int n = nums.length;
    int[][] elements = new int[n][2];
    for (int i = 0; i < n; i++) {
      elements[i] = new int[]{nums[i], i};
    }
    Arrays.sort(elements, (arr1, arr2) -> arr1[0] == arr2[0] ? arr1[1] - arr2[1] : arr1[0] - arr2[0]);
    int m = l.length, pre = 0, diff = 0;
    boolean first, second;
    List<Boolean> list = new ArrayList<>(m);
    flag:
    for (int i = 0; i < m; i++) {
      first = false;
      second = false;
      for (int[] e : elements) {
        if (e[1] > r[i] || e[1] < l[i]) {
          continue;
        }
        if (!first) {
          first = true;
        } else if (!second) {
          diff = e[0] - pre;
          second = true;
        } else if (e[0] - pre != diff) {
          list.add(false);
          continue flag;
        }
        pre = e[0];
      }
      list.add(true);
    }
    return list;
  }

  public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
    int m = l.length;
    List<Boolean> list = new ArrayList<>(m);
    Set<Integer> set = new HashSet<>();
    int min, max, diff, maxDiff, maxDistance;
    flag:
    for (int i = 0; i < m; i++) {
      min = nums[l[i]];
      max = nums[l[i]];
      set.clear();
      set.add(nums[l[i]]);
      for (int j = l[i] + 1; j <= r[i]; j++) {
        if (nums[j] > max) {
          max = nums[j];
        }
        if (nums[j] < min) {
          min = nums[j];
        }
        set.add(nums[j]);
      }
      if ((maxDiff = max - min) == 0) {
        list.add(true);
        continue;
      }
      maxDistance = r[i] - l[i];
      if (set.size() != maxDistance + 1 || maxDiff % maxDistance != 0) {
        list.add(false);
        continue;
      }
      diff = maxDiff / maxDistance;
      for (int j = l[i]; j <= r[i]; j++) {
        if ((nums[j] - min) % diff != 0) {
          list.add(false);
          continue flag;
        }
      }
      list.add(true);
    }
    return list;
  }

  // 1626. 无矛盾的最佳球队
  public int bestTeamScore(int[] scores, int[] ages) {
    int n = scores.length;
    int[][] players = new int[n][2];
    for (int i = 0; i < n; i++) {
      players[i] = new int[]{scores[i], ages[i]};
    }
    Arrays.sort(players, (p1, p2) -> p1[1] == p2[1] ? p1[0] - p2[0] : p1[1] - p2[1]);
    int[] dp = new int[n];
    int result = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) {
        if (players[j][0] <= players[i][0] && dp[j] > dp[i]) {
          dp[i] = dp[j];
        }
      }
      dp[i] += players[i][0];
      result = Math.max(result, dp[i]);
    }
    return result;
  }

  // 1616. 分割两个字符串得到回文串
  public boolean checkPalindromeFormation(String a, String b) {
    int n = a.length();
    return doCheckPalindromeFormation(n, a, b) || doCheckPalindromeFormation(n, b, a);
  }

  private boolean doCheckPalindromeFormation(int n, String a, String b) {
    int left = 0, right = n - 1;
    while (left < right && a.charAt(left) == b.charAt(right)) {
      left++;
      right--;
    }
    if (left >= right) {
      return true;
    }
    return isPalindrome(a, left, right) || isPalindrome(b, left, right);
  }

  private boolean isPalindrome(String s, int start, int end) {
    while (start < end && s.charAt(start) == s.charAt(end)) {
      start++;
      end--;
    }
    return start >= end;
  }


  // 1615. 最大网络秩
  public int maximalNetworkRank(int n, int[][] roads) {
    boolean[][] access = new boolean[n][n];
    int[] degree = new int[n];
    for (int[] road : roads) {
      access[road[0]][road[1]] = true;
      access[road[1]][road[0]] = true;
      degree[road[0]]++;
      degree[road[1]]++;
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        max = Math.max(degree[i] + degree[j] - (access[i][j] ? 1 : 0), max);
      }
    }
    return max;
  }

  // 1605. 给定行和列的和求可行矩阵
  public int[][] restoreMatrix1(int[] rowSum, int[] colSum) {
    int rows = rowSum.length;
    int cols = colSum.length;
    int[][] result = new int[rows][cols];
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        result[i][j] = Math.min(rowSum[i], colSum[j]);
        rowSum[i] -= result[i][j];
        colSum[j] -= result[i][j];
      }
    }
    return result;
  }

  public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
    int i = 0, j = 0, minimum = 0, m = rowSum.length, n = colSum.length;
    int[][] grid = new int[m][n];
    while (i < m && j < n) {
      minimum = grid[i][j] = Math.min(rowSum[i], colSum[j]);
      if ((rowSum[i] -= minimum) == 0) {
        i++;
      }
      if ((colSum[j] -= minimum) == 0) {
        j++;
      }
    }
    return grid;
  }

  // 1590. 使数组和能被 P 整除
  public int minSubarray(int[] nums, int p) {
    int len = nums.length, remain = 0;
    for (int i = 0; i < len; i++) {
      nums[i] %= p;
      remain = (int) (((long) remain + nums[i]) % p);
    }
    if (remain == 0) {
      return 0;
    }
    long[] helper = new long[len];
    helper[0] = nums[0];
    for (int i = 1; i < len; i++) {
      helper[i] = helper[i - 1] + nums[i];
    }
    long innerSum;
    for (int i = 1; i <= len - 1; i++) {
      for (int start = 0; start <= len - i; start++) {
        innerSum = helper[start + i - 1] - (start == 0 ? 0 : helper[start - 1]);
        if (innerSum % p == remain) {
          return i;
        }
      }
    }
    return -1;
  }

  // 剑指 Offer 47. 礼物的最大价值
  public int maxValue(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    int left, up;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        left = j == 0 ? 0 : f[i][j - 1];
        up = i == 0 ? 0 : f[i - 1][j];
        f[i][j] = Math.max(left, up) + grid[i][j];
      }
    }
    return f[m - 1][n - 1];
  }

  // 1487. 保证文件名唯一
  public String[] getFolderNames(String[] names) {
    int len = names.length;
    String[] result = new String[len];
    Map<String, Integer> map = new HashMap<>(len);
    Integer count;
    String s;
    int k;
    for (int i = 0; i < len; i++) {
      count = map.get(names[i]);
      if (count == null) {
        result[i] = names[i];
        map.put(names[i], 1);
      } else {
        k = count;
        while (map.containsKey(s = names[i] + "(" + k + ")")) {
          k++;
        }
        result[i] = s;
        map.put(names[i], k + 1);
        map.put(s, 1);
      }
    }
    return result;
  }

  // 1238. 循环码排列
  public List<Integer> circularPermutation(int n, int start) {
    int numberCount = (1 << n);
    List<Integer> list = new ArrayList<>(numberCount);
    for (int i = 0; i < numberCount; i++) {
      list.add(i ^ (i >> 1) ^ start);
    }
    return list;
  }

  // 89. 格雷编码
  public List<Integer> grayCode1(int n) {
    List<Integer> list = new ArrayList<>();
    list.add(0);
    list.add(1);
    if (n == 1) {
      return list;
    }
    int size;
    for (int i = 1; i < n; i++) {
      size = list.size();
      for (int j = size - 1; j >= 0; j--) {
        list.add((1 << i) | list.get(j));
      }
    }
    return list;
  }

  public List<Integer> grayCode(int n) {
    int numberCount = (1 << n);
    List<Integer> list = new ArrayList<>(numberCount);
    for (int i = 0; i < numberCount; i++) {
      list.add(i ^ (i >> 1));
    }
    return list;
  }

  // 1792. 最大平均通过率
  public double maxAverageRatio1(int[][] classes, int extraStudents) {
    double sumRate = 0, maxDiff = Integer.MIN_VALUE;
    int bakIndex = -1;
    int len = classes.length;
    double[] rateIfAdded = new double[len];
    for (int i = 0; i < len; i++) {
      rateIfAdded[i] = diff(classes[i][0], classes[i][1]);
      if (rateIfAdded[i] > maxDiff) {
        maxDiff = rateIfAdded[i];
        bakIndex = i;
      }
    }
    classes[bakIndex][0]++;
    classes[bakIndex][1]++;
    rateIfAdded[bakIndex] = diff(classes[bakIndex][0], classes[bakIndex][1]);
    while (extraStudents > 1) {
      maxDiff = -1;
      for (int i = 0; i < len; i++) {
        if (rateIfAdded[i] > maxDiff) {
          maxDiff = rateIfAdded[i];
          bakIndex = i;
        }
      }
      classes[bakIndex][0]++;
      classes[bakIndex][1]++;
      rateIfAdded[bakIndex] = diff(classes[bakIndex][0], classes[bakIndex][1]);
      extraStudents--;
    }
    for (int[] p : classes) {
      sumRate += (double) p[0] / p[1];
    }
    return sumRate / len;
  }

  private double diff(double m, double n) {
    return (1 - m / n) / (n + 1);
  }

  public double maxAverageRatio(int[][] classes, int extraStudents) {
    PriorityQueue<int[]> queue = new PriorityQueue<>((p1, p2) -> {
      int n1 = p1[1];
      int n2 = p2[1];
      return -Long.compare((long) n2 * (n2 + 1) * (n1 - p1[0]), (long) n1 * (n1 + 1) * (n2 - p2[0]));
    });
    queue.addAll(Arrays.asList(classes));
    for (int i = 0; i < extraStudents; i++) {
      int[] curr = queue.poll();
      if (curr == null) {
        continue;
      }
      curr[0]++;
      curr[1]++;
      queue.offer(curr);
    }
    double sumRate = 0;
    for (int[] p : queue) {
      sumRate += (double) p[0] / p[1];
    }
    return sumRate / classes.length;
  }

  // 1237. 找出给定方程的正整数解
  public List<List<Integer>> findSolution1(CustomFunction customfunction, int z) {
    List<List<Integer>> list = new ArrayList<>();
    int y, result;
    for (int x = 1; x <= 1000; x++) {
      y = 1;
      for (; y <= 1000; y++) {
        result = customfunction.f(x, y);
        if (result == z) {
          list.add(Arrays.asList(x, y));
        }
        if (result >= z) {
          break;
        }
      }
      if (y == 1) {
        break;
      }
    }
    return list;
  }

  public List<List<Integer>> findSolution(CustomFunction function, int z) {
    List<List<Integer>> list = new ArrayList<>();
    int result;
    for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
      while ((result = function.f(x, y)) > z && y >= 1) {
        y--;
      }
      if (y >= 1 && result == z) {
        list.add(Arrays.asList(x, y));
      }
    }
    return list;
  }

  // 1124. 表现良好的最长时间段
  public int longestWPI(int[] hours) {
    int maxLength = hours.length;
    int diff = 0;
    int[] cache = new int[maxLength];
    for (int i = 0; i < maxLength; i++) {
      diff += (hours[i] > 8 ? 1 : -1);
      cache[i] = diff;
    }
    int j, curr;
    for (int len = maxLength; len > 0; len--) {
      for (int i = 0; i <= maxLength - len; i++) {
        j = i + len - 1;
        curr = i == 0 ? cache[j] : cache[j] - cache[i - 1];
        if (curr > 0) {
          return len;
        }
      }
    }
    return 0;
  }

  // 1234. 替换子串得到平衡字符串
  public int balancedString(String s) {
    // TODO 未完成
    return -1;
  }

  // 1129. 颜色交替的最短路径
  public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
    int[] answer = new int[n];
    for (int i = 1; i < n; i++) {
      answer[i] = -1;
    }
    int[] pre = new int[n];
    for (int[] edge : redEdges) {
      pre[edge[1]] = edge[0];
      answer[edge[1]] = answer[edge[0]] + 1;
    }
    for (int[] edge : blueEdges) {
      pre[edge[1]] = edge[0];
      answer[edge[1]] = answer[edge[0]] + 1;
    }
    return answer;
  }

  // 1233. 删除子文件夹
  public List<String> removeSubfolders(String[] folder) {
    Set<String> container = new HashSet<>(Arrays.asList(folder));
    List<String> list = new ArrayList<>();
    String k;
    for (String s : folder) {
      k = s;
      do {
        k = k.substring(0, k.lastIndexOf("/"));
      } while (k.length() > 0 && !container.contains(k));
      if (k.length() == 0) {
        list.add(s);
      }
    }
    return list;
  }

  // 1664. 生成平衡数组的方案数
  public int waysToMakeFair(int[] nums) {
    int oddSum = 0, evenSum = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
      if ((i & 1) == 0) {
        evenSum += nums[i];
      } else {
        oddSum += nums[i];
      }
    }
    int sum = 0;
    int diff = evenSum - oddSum;
    boolean currEven;
    for (int i = 0; i < len; i++) {
      currEven = ((i & 1) == 0);
      if (currEven) {
        diff -= nums[i];
      } else {
        diff += nums[i];
      }
      if (diff == 0) {
        sum++;
      }
      if (currEven) {
        diff -= nums[i];
      } else {
        diff += nums[i];
      }
    }
    return sum;
  }

  // 1813. 句子相似性 III
  public boolean areSentencesSimilar(String sentence1, String sentence2) {
    String[] part1 = sentence1.split(" ");
    String[] part2 = sentence2.split(" ");
    int len1 = part1.length;
    int len2 = part2.length;
    int minLen = Math.min(len1, len2);
    int i = 0, j = 0;
    while (i < minLen && part1[i].equals(part2[i])) {
      i++;
    }
    while (j < minLen - i && part1[len1 - 1 - j].equals(part2[len2 - 1 - j])) {
      j++;
    }
    return (i + j) == minLen;
  }

  // 面试题 17.09. 第 k 个数
  public int getKthMagicNumber(int k) {
    int[] result = new int[k];
    result[0] = 1;
    int p3 = 0, p5 = 0, p7 = 0;
    int n3, n5, n7;
    for (int i = 1; i < k; i++) {
      n3 = result[p3] * 3;
      n5 = result[p5] * 5;
      n7 = result[p7] * 7;
      result[i] = Math.min(Math.min(n3, n5), n7);
      if (result[i] == n3) {
        p3++;
      }
      if (result[i] == n5) {
        p5++;
      }
      if (result[i] == n7) {
        p7++;
      }
    }
    return result[k - 1];
  }

  // 973. 最接近原点的 K 个点
  public int[][] kClosest1(int[][] points, int k) {
    int len = points.length;
    if (k >= len) {
      return points;
    }
    Map<Integer, Integer> map = new TreeMap<>();
    for (int i = 0; i < len; i++) {
      map.put(i, calculateDistance(points[i]));
    }
    int[][] result = new int[k][2];
    List<Integer> collect = map.values().stream().sorted().limit(k).collect(Collectors.toList());
    int c = 0;
    for (int i = 0; i < len; i++) {
      if (collect.contains(map.get(i))) {
        result[c++] = points[i];
      }
    }
    return result;
  }

  public int[][] kClosest(int[][] points, int k) {
    Arrays.sort(points, Comparator.comparingInt(this::calculateDistance));
    return Arrays.copyOfRange(points, 0, k);
  }

  private int calculateDistance(int[] location) {
    return location[0] * location[0] + location[1] * location[1];
  }

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    return null;
  }
}
